1. Field of the Invention
This invention relates to networks for data communications. More specifically, this invention relates to the allocation of transmission rates among the producers in a data communications network. More specifically, this invention relates to the allocation of transmission rates on the reverse link of a wireless data communications network.
2. Description of Related Art and General Background
Channel capacity, a basic limitation of any system for data communications, may be defined as the rate at which information can be passed from one end of a transmission channel to the other, given some mode of transmission and some performance criteria (e.g., binary phase-shift keying modulation of a 1.9-GHz RF carrier using polar NRZ signaling, with a bit-error rate of 10−5). The rate at which information may be transferred from one point to another cannot exceed the ability of the particular method and medium of transmission to convey that information intelligibly. It follows that the rate at which a data producer outputs data into a transmission channel cannot exceed the channel capacity, commonly measured in units of information per units of time (e.g., Kbits/s).
Digital data are commonly transmitted in frames of predetermined length. In order to allow for error detection, it is also common to calculate and transmit a checksum along with each frame, so that the data may be verified by the receiver. This checksum is typically in the form of a cyclic redundancy check (CRC) value computed with a polynomial algorithm known to both the receiver and the transmitter. If the data in the received frame do not match the received checksum, the frame is rejected and must be re-transmitted or compensated for in another manner.
Two or more producers may wish to transmit information over the same channel. If, for example, the producers are also physically separated, then their transmissions may not be coordinated with each other. A data collision occurs when the several transmissions arrive at the consumer having together exceeded the available channel capacity. (Note that in a time-division multiple-access or TDMA wireless system, the channel capacity available to any producer may change over time as a function of the number of producers using the same frequency channel, in that the available capacity will be zero during any period when another producer is using the channel.) Such a collision causes all of the frames being transmitted to become irretrievably corrupted, no matter how complete their transmissions were to that point. If re-transmission is required (i.e., if the system cannot otherwise compensate for the loss of data), then the producers must re-send these frames in their entirety. Therefore, one may clearly see that data collisions directly and dramatically reduce the effective channel capacity.
When the sum of the producers' output rates may exceed the channel capacity, then the producers are competing for the same limited resource and some method of allocating the channel capacity among them becomes necessary. Such allocation methods may be static, dynamic, or some combination of the two.
Static allocation schemes are best suited for situations where the data producers' outputs remain relatively constant over time: in systems for voice transmission, for example. (We will assume here that the capacity of the channel itself remains relatively constant.) One characteristic of static allocation schemes is that they may be applied in a similar fashion to either wired or wireless networks. For example, several digitized voice signals may be time-division multiplexed over a single copper or fiber optic cable, or a number of analog voice signals may be time- and/or frequency-division multiplexed over the same radio frequency band, or several digitized voice signals may share the same radio frequency band at the same time by using code-division multiple access techniques.
Alternatively, the rates of data production may vary significantly from one moment to the next; i.e., the data traffic may be bursty. Traffic on high speed networks for data communications, for example, tends to be bursty. Static allocation techniques are not well suited for such environments. On one hand, data transmission applications are usually more tolerant of delays than voice transmission applications, so a producer will not usually require the regulated level of access to the channel which a static scheme provides. On the other hand, while backlogged and therefore outdated voice information may simply be discarded by the producer before transmission, discarding data information whose transmission has been delayed is not usually a viable option. Therefore, if a producer's store of data information should begin to accumulate faster than its buffering capacity can handle, the producer will temporarily need to use more of the channel capacity than it has been assigned. Even if other producers are currently idle, however, and plenty of channel capacity is presently available, a static scheme will not accommodate the temporary redistribution of capacity needed in this situation.
Suppose that a channel has a capacity of 200 Kbits/s; there are four producers A, B, C, and D, each having a maximum output rate of 200 Kbits/s; and 50 Kbits/s of the capacity as statically allocated to each producer. If each producer produces a steady stream of data at the allocated rate of 50 Kbits/s, then the allocation scheme may be said to be optimal. However, if instead, the traffic is bursty, with A having a packet of 50 Kbits to output at time 0.25 s, B and C each having a packet of 50 Kbits to output at time 0.5 s, and D having a packet of 50 Kbits to output at time 0.75 s. As shown in FIG. 1, 1 second is required for each producer to complete its transmission under the static scheme described above, even though it would take only 0.25 second if the producer were allowed to operate at its maximum output rate. It is notable that using a static allocation scheme in this bursty environment also causes much of the channel capacity to remain unused.
Now consider FIG. 2, in which channel capacity is allocated dynamically according to each producer's ability to use the channel during any given quarter-second. At time 0, only producer A has data to transmit. Therefore, we allocate the entire channel capacity of 200 Kbits/s to producer A, and it completes its task in 0.25 s, for a 75% savings over the static allocation scheme. At time 0.5 s, producers B and C each have data to transmit, so we allocate 50% of the channel capacity to each one, and they complete their tasks in 0.5 s, for a savings of 50%. (Note that a more optimal scheme would allow either B or C to use the entire channel, completing transmission in 0.25 s. The other producer would still complete in 0.5 s, using the entire channel between times 0.75 and 1.0 s.)
At time 0.75 s, producer D has also data to transmit. We will assume that the scheme requires D to wait until producers B and C have finished, so that D begins transmission at 200 Kbits/s at time 1.0 s and finishes at 1.25 s, for a savings of 50%. Therefore, it is clear that in this bursty environment dynamic allocation can achieve an average savings in time with respect to each producer of greater than 50%.
As noted above, we have assumed that the capacity of the channel remains relatively constant. This assumption will not always hold in the real world, especially in cases where the channel is wireless. When the total capacity drops, a system that is using the full capacity of the channel under a purely static scheme will fail. A dynamic scheme, on the other hand, can usually be adapted to base its allocations on an updated report of the total capacity rather than on some fixed value.
For all of their advantages, however, dynamic allocation schemes may be much more complicated to implement than static ones. In static allocation, a fixed set of rules is developed and applied, and the only task during operation is to ensure compliance with these rules. In dynamic allocation, on the other hand, the rules must adapt continually to match a changing environment. An implicit requirement for a dynamic scheme, therefore, is a way for the allocation mechanism to acquire knowledge about the environment: i.e., which of the producers has data to transmit, and how much.
Note that in the discussion of FIG. 2 above, we have assumed that the allocation mechanism has perfect knowledge of when each producer has data to transmit and how much data it has to transmit. In many applications, however, it may not be possible for the allocation mechanism to obtain or otherwise determine any of this information directly. We have also assumed that the amount of data that each producer has to transmit is not changing, and that each producer has enough power to transmit at the allocated rate. In many situations, one or both of these assumptions may not hold.
Also note that under a static allocation scheme, data collisions cannot occur, assuming that the actual channel capacity does not decrease and that the rules are chosen so that the sum of all allocated rates does not exceed that capacity. In dynamic schemes, however, the rules are based on a necessarily imperfect model of the future behavior of the producers. Collisions become possible, and this possibility must be considered in any evaluation of dynamic allocation schemes.
Mainly because of the requirement for knowledge of the environment, implementations of dynamic allocation schemes on wired links differ significantly from implementations on wireless links. In a wired service such as Ethernet, for example, the producers can monitor the channel at the same time they are transmitting over it; no particular problem is caused by creating voltage fluctuations on a wire on one hand, and monitoring the voltage fluctuations on that wire on the other hand. This immediate availability of feedback information to all users of a wire channel allows for distributed control of the channel. Not only can each producer listen to the channel before transmission to make sure it is clear, but the producer can also monitor its own ongoing transmission to make sure that it is not colliding with a simultaneous transmission by another producer. When a collision occurs, the relevant producers know about it and can react without delay.
In wireless systems, however, simultaneous transmission and reception over the same channel is not commonly implemented. One reason is the significant problem of monitoring the channel for remote activity being masked by a simultaneous and much stronger local signal. Even if this difficulty is overcome, however, it may still be impossible for a producer to determine when a collision has occurred at the consumer.
In one simple example, the signals of two producers may collide at the consumer, but be prevented from reaching each other. Detecting no conflict, each producer will believe that its transmission was successful, when in fact no data was actually received by the consumer. This example illustrates the problem that in a wireless system, the producers typically have no direct way to obtain meaningful feedback information concerning current channel use. Such information can typically only be obtained indirectly from a unit at the other end of the channel. Consequently, data collisions caused by channel overuse become more costly in a wireless network because of the feedback delay.
One conventional approach to dynamic allocation in wireless networks is the well-known ALOHA scheme. In ALOHA, transmissions are divided into frames, and any producer may transmit a data frame at any time. If the frame is acknowledged by the channel control unit, then the producer assumes that it was transferred successfully. If the frame is not acknowledged, then the producer assumes that it collided with a transmission by another producer, and it re-transmits the frame at a future time according to some delay protocol.
Unfortunately, ALOHA is extremely susceptible to data collisions, and it can be demonstrated that the maximum channel utilization for a pure ALOHA scheme is only 18%. An improved version, called slotted ALOHA, requires transmissions to be initiated only on slot boundaries, where the time between adjacent slot boundaries corresponds to the time required to transmit one frame. Slotted ALOHA thus doubles the maximum utilization to 37% by reducing the collision interval from two slots to only one. However, over 60% of the channel capacity is still lost due to collision or inactivity. (In this case, 37% of the slots are used for successful transmissions, 37% remain idle, and 26% are lost to collisions. Trying to reduce the number of idle slots increases the rate of collision and thus reduces the number of successful transmissions).
Another type of dynamic allocation scheme is the request-grant method, several variations of which exist in practice. In a request-grant system, each producer transmits a request for a certain portion of the channel capacity, and a control unit considers the various requests and transmits allocation grants back to the producers.
One problem with using a request-grant system is that a producer may not know in advance how much of the channel capacity it will need. Consider a producer made up of a buffer memory unit connected to a wireless telephone through, e.g., a PCMCIA interface. Ideally, the telephone will remain off-the-air until the buffer is full, at which time it will request permission to transmit the contents of the buffer at maximum rate in a single burst. Unfortunately, unless the buffer unit and the telephone are purchased as a single device, the capacity of the buffer will generally not be known to the telephone. Also, there may be an additional store of data ready for transmission and waiting on the other side of the buffer. Therefore, the telephone typically will not know how much data is actually available for transmission, and consequently it will not know what rate to request.
Other problems associated with request-grant systems are the extra traffic required to send the requests (which necessarily reduces the available channel capacity) and the delays incurred in waiting for requests to be received, processed, and acknowledged. Transmission over a common channel is also susceptible to the abrupt changes in channel quality that may occur when another producer suddenly begins to use a large allocation grant.